package datastructure.book.tujiesuanfa.queueastack.exercise.first;

import java.util.LinkedList;
import java.util.Objects;

/**
 *  最小栈 提供 push ，pop ，top 操作，
 *  并能在常数时间内检索到最小元素的栈
 *  所有方法时间复杂度均为O(1)
 */
public class MinStack {

    private final LinkedList<Integer> stack = new LinkedList<>();
    private final LinkedList<Integer> minValueStack = new LinkedList<>();

    public MinStack() {

    }

    public void push(int x) {
        stack.addLast(x);
        if (minValueStack.isEmpty() || minValueStack.getLast() >= x) {
            minValueStack.add(x);
        }
    }

    public void pop() {
        Integer i = stack.removeLast();
        if (Objects.equals(minValueStack.getLast(), i)) {
            minValueStack.removeLast();
        }
    }

    /**
     * 空，返回-1
     */
    public int top() {
        if (stack.isEmpty()) {
            return -1;
        }
        return stack.getLast();
    }
    /**
     * 空，返回-1
     */
    public int getMin() {
        if (stack.isEmpty()) {
            return -1;
        }
        return minValueStack.getLast();
    }
}
